package com.fucius.study.leetcode;

/**
 * 4. 丑数 II
 * 中文English
 * 设计一个算法，找出只含素因子2，3，5 的第 n 小的数。
 *
 * 符合条件的数如：1, 2, 3, 4, 5, 6, 8, 9, 10, 12...
 *
 * 样例
 * 样例 1：
 *
 * 输入：9
 * 输出：10
 * 样例 2：
 *
 * 输入：1
 * 输出：1
 * 挑战
 * 要求时间复杂度为 O(nlogn) 或者 O(n)。
 *
 * 注意事项
 * 我们可以认为 1 也是一个丑数。
 */
public class NthUglyNumber {
    /**
     * 动态规划  O(n)
     * 求第K项问题 优先想到动态规划
     * @param n: An integer
     * @return: return a  integer as description.
     */
    public int nthUglyNumber(int n) {
        int[] data = new int[n];
        data[0] = 1;
        int i = 1;
        int i2 = 0 , i3 = 0, i5 = 0;
        while(i < n){
            data[i] = Math.min(Math.min(data[i2]*2,data[i3]*3),data[i5]*5);
            if(data[i] == data[i2] * 2){
                i2++;
            }
            if(data[i] == data[i3] * 3){
                i3++;
            }
            if(data[i] == data[i5] * 5){
                i5++;
            }
            i++;
        }
        return data[n-1];
    }
}
